/**
 * 剑指 Offer 37. 序列化二叉树
 * https://leetcode-cn.com/problems/xu-lie-hua-er-cha-shu-lcof/
 */
const { createTreeNode, TreeNode, displayTreeNode } = require('../../libs/public');

function concat(str, val, count) {
  val = val === null ? '' : val;
  const newPart = count === 1 ? String(val) : `${val}_${count}`;
  return str ? `${str},${newPart}` : newPart;
}

/**
 * Encodes a tree to a single string.
 *
 * @param {TreeNode} root
 * @return {string}
 */
function serialize(root) {
  if (!root) {
    return '';
  }
  const stack = [root.left, root.right];
  let result = '';
  let lastVal = root.val;
  let lastValCount = 1;
  while (stack.length) {
    const node = stack.shift();
    if (node === null) {
      // eslint-disable-next-line no-lonely-if
      if (lastVal === null) {
        lastValCount += 1;
      } else {
        result = concat(result, lastVal, lastValCount);
        lastVal = null;
        lastValCount = 1;
      }
    } else {
      if (node.val === lastVal) {
        lastValCount += 1;
      } else {
        result = concat(result, lastVal, lastValCount);
        lastVal = node.val;
        lastValCount = 1;
      }
      stack.push(node.left, node.right);
    }
  }
  if (lastVal !== null) {
    result = concat(result, lastVal, lastValCount);
  }
  return result;
}

/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}
 */
function deserialize(data) {
  if (!data) {
    return null;
  }
  let i = 0;
  const stack = [];
  let root = null;
  let lastNode = null;
  while (i < data.length) {
    let val;
    let count;
    const begin = i;
    let end = data.indexOf(',', begin);
    if (end < 0) {
      end = data.length;
    }
    const splitIndex = data.indexOf('_', begin);
    if (splitIndex < 0 || splitIndex > end) {
      val = data.substring(begin, end);
      count = 1;
    } else {
      val = data.substring(begin, splitIndex);
      count = parseInt(data.substring(splitIndex + 1, end), 10) || 1;
    }
    if (val) {
      val = parseInt(val, 10);
    } else {
      val = null;
    }
    while (count) {
      const node = val === null ? null : new TreeNode(val);
      if (root) {
        if (lastNode) {
          lastNode.right = node;
          lastNode = null;
        } else {
          lastNode = stack.shift();
          lastNode.left = node;
        }
        if (node) {
          stack.push(node);
        }
      } else {
        root = node;
        stack.push(node);
      }
      count -= 1;
    }
    i = end + 1;
  }
  return root;
}

console.log(
  displayTreeNode(deserialize(serialize(createTreeNode([]))))
  === '[]',
);
console.log(
  displayTreeNode(deserialize(serialize(createTreeNode([1]))))
  === '[1]',
);
console.log(
  displayTreeNode(deserialize(serialize(createTreeNode([1, 2, 3, null, null, 4, 5]))))
  === '[1,2,3,null,null,4,5]',
);
console.log(
  displayTreeNode(deserialize(serialize(createTreeNode([1, 2, 3, null, 6, 4, 5]))))
  === '[1,2,3,null,6,4,5]',
);
console.log(
  displayTreeNode(deserialize(serialize(createTreeNode([0, 0, 0, 0, null, null, 1, null, null, null, 2]))))
  === '[0,0,0,0,null,null,1,null,null,null,2]',
);
